
/*
散列表，哈希表
*/
const ValuePair = require('./ValuePair');
const LinkedList = require('./LinkedList');

class HashMap {
    constructor() {
      this.table = {}
    }
    hashCode(key) {
      if(typeof key === 'number') {
        return key;
      }
      let tableKey = keyToString(key)
      let hash = 0;
      for(let i = 0; i < tableKey.length; i++) {
        hash += tableKey.charCodeAt(i)
      }
      return Math.ceil(hash / 20);
    }
}
  function keyToString(item) {
    if(item === null) {
      return 'NULL'
    }
    if(item === undefined) {
      return 'UNDEFINED'
    }
    if(item instanceof String) {
      return `${item}`
    }
    return item.toString()
  }
  HashMap.prototype.put = function(key, value) {
    //this.table[keyToString(key)] = value
    if(key !== null && value !== null) {
        let pos = this.hashCode(key)
        this.table[pos] = new ValuePair(key, value)
        return true;
      }
      return false;
  }
  HashMap.prototype.get = function(key) {
    //return this.table[keyToString(key)]
    let valuePair = this.table[this.hashCode(key)] 
    return valuePair ? valuePair.value : undefined;
  }
  HashMap.prototype.remove = function(key) {
    delete this.table[keyToString(key)]
  }
  HashMap.prototype.size = function() {
    return Object.keys(this.table).length
  }
  HashMap.prototype.isEmpty = function() {
    return this.size() === 0
  }
  HashMap.prototype.clear = function() {
    this.table = {}
  }
  HashMap.prototype.keys = function() {
    return Object.keys(this.table)
  }
  HashMap.prototype.values = function() {
    return Object.values(this.table)
  }
  HashMap.prototype.toString = function() {
    return JSON.stringify(this.table)
  }

//分离链接法是指在散列表存储数据时，value 部分用 链表 来代替之前的 键值对。
//键值对只能存储一个，而链表可以存储多个键值对。
//如果遇到相同的散列值，则在已有的链表中添加一个键值对即可。
//
  class HashTableSeparateChaining extends HashMap {
    constructor() {
      super()
      this.table = {}
    }
    put(key, value) {
      if(key !== null && value !== null) {
        let pos = this.hashCode(key)
        if(!this.table[pos]) {
          this.table[pos] = new LinkedList()
        }
        this.table[pos].push(new ValuePair(key, value))
        return true;
      }
      return false;
    }
    get(key) { 
      let linkedList = this.table[this.hashCode(key)]
      if(linkedList && !linkedList.isEmpty()) {
        let current = linkedList.getItemAt(0);
        while(current) {
          if(current.value.key === key) {
            return current.value.value
          }
          current = current.next
        }
      }
      return undefined; 
    }
    remove(key) { 
      let pos = this.hashCode(key)
      let linkedList = this.table[pos]
      if(linkedList && !linkedList.isEmpty()) {
        let index = 0;
        let current = linkedList.getItemAt(index);
        while(current) {
          if(current.value.key === key) {
            linkedList.removeAt(index)
            if(linkedList.isEmpty()) {
              delete this.table[pos]
            }
            return true;
          }
          current = current.next;
          index++;
        }
      }
      return false;
    }
  }

  //线性探查法是指当散列值重复的时候，试着将散列值叠加，直到其变成唯一的值。
  class HashTableLinearProbing extends HashMap {
    constructor() {
      super()
      this.table = {}
    }
    put(key, value) {
      if(key && value) {
        let pos = this.hashCode(key);
        while(this.table[pos]) {
          pos++;
        }
        this.table[pos] = new ValuePair(key, value);
        return true;
      }
      return false;
    }
    get(key) {
      let pos = this.hashCode(key);
      if(this.table[pos]) {
        if(this.table[pos].key === key) {
          return this.table[pos].value
        }
        let index = pos + 1;
        while(this.table[index] && this.table[index].key !== key) {
          index++;
        }
        if(this.table[index] && this.table[index].key === key) {
          return this.table[index].value
        }
      }
      return undefined;
    }
    remove(key) {
      let pos = this.hashCode(key);
      if(this.table[pos]) {
        if(this.table[pos].key === key) {
          delete this.table[pos]
          this.verifyRemoveSideEffect(key, pos)
          return true
        }
        let index = pos + 1;
        while(this.table[index] && this.table[index].key !== key) {
          index++;
        }
        if(this.table[index] && this.table[index].key === key) {
          delete this.table[index]
          this.verifyRemoveSideEffect(key, index)
          return true
        }
      }
      return false;
    }
    verifyRemoveSideEffect(key, pos) { 
      const hash = this.hashCode(key); 
      let index = pos + 1; // {2} 
      while (this.table[index] != null) { // {3} 
        const posHash = this.hashCode(this.table[index].key); // {4} 
        if (posHash <= hash || posHash <= pos) { // {5}
          this.table[pos] = this.table[index]; // {6} 
          delete this.table[index]; 
          pos = index; 
        } 
        index++; 
      }
    }
  }

// const hashMap = new HashMap()
// hashMap.put('name', 'John')
// hashMap.put('age', 30)
// hashMap.put('city', 'New York')
// console.log(hashMap.get('name')) // John
// console.log(hashMap.get('age')) // 30
// console.log(hashMap.get('city')) // NewYork


var hashtable = new HashTableSeparateChaining();
hashtable.put("name", "杨成功");
hashtable.put("mane", "成功杨");
console.log(hashtable.table);

console.log(hashtable.get("name")); // 杨成功
console.log(hashtable.get("mane")); // 成功杨
console.log(hashtable.get("sex")); // undefined

console.log(hashtable.remove("name")); // true
console.log(hashtable.remove("name")); // false
console.log(hashtable.table);

// var hashtable = new HashTableLinearProbing();
// hashtable.put("name", "杨成功");
// hashtable.put("mane", "成功杨");
// console.log(hashtable.table);

  module.exports = HashMap
